Multi-core processors (chip multi-processors) in which a plurality of processor cores are integrated on one chip have been released one after another from respective microprocessor manufacturers. In the fields of information home electric appliances and device embedding (such as cellular phones, game machines, car navigation systems, digital television receivers, HDD/DVD recorders/players), as well as in the fields of super computers, servers, desktop computers, and PC servers, there is a trend toward employment of multi-core microprocessors.
In this way, the multi-core processors are used at present in most of information devices ranging from the information home electric appliances to the super computers, and it is expected that the multi-core processor will be integrated into more information devices in the future.
The multi-core processor can utilize not only parallelism on the fine grain instruction level, but also parallelism on the loop level having larger parallelism, parallelism between loops with coarser granularity, and rough grain task parallelism between functions. In this way, the multi-core processor is advantageous in, by using larger parallelism, increasing processing performance of a processor. Moreover, the multi-core processor can attain the same performance by using n processor cores, and hence, by decreasing the clock frequency to one n-th and by decreasing a voltage to be applied, the multi-core processor is also advantageous in capability of keeping power consumption (which increases with the square of the voltage) low.
Moreover, in terms of software, parallel programming for the multi-core processor usually requires a large amount of time for tuning, and, thus, development of application software is troublesome. However, a relatively small number of processors are presently integrated, and hence it is possible to obtain a high performance by means of an automatic parallelizing compiler which automatically parallelizes a sequential program. In the field of the information home electric appliances, quality and the number of applications determine competitiveness in the market, and hence, when the automatic parallelizing of a program for four-core, eight-core, and sixteen-core multi-processor is possible by a compiler, advantage of multi-core configuration increases.
Moreover, as multi-grain parallelizing, a technology of, by combining all parallelisms such as those on a statement-level, a loop-level, and a more coarse level (such as between loops, between subroutines, and between basic blocks), by means of the earliest executable condition analysis, for extracting a parallelism is disclosed in JP 2001-175619 A.